package com.ww.springboot.boot.algorithm.list;

import java.util.ArrayList;
import java.util.List;

/**
 * 寻找两个正序数组的中位数
 * <p>
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * <p>
 * 解题思路1. 顺序过滤两数组数字 直到过滤数量到中位数时 输出中位数
 *
 * @author wanwei
 * @since 2021-03-06 14:55
 */
public class FindMedianSortedArrays {

    public static void main(String[] args) {
        int[] array1 = {2};
        int[] array2 = {};
        System.out.println(method(array1, array2));
    }

    private static double method(int[] nums1, int[] nums2) {
        int totalNum = nums1.length + nums2.length;
        int m = 0;
        int n = 0;
        int total = 0;

        int remainder = totalNum % 2;
        int divisor = totalNum / 2;

        List<Integer> list = new ArrayList<>();
        while (true) {
            int num = 0;
            if (m < nums1.length && n < nums2.length) {
                if (nums1[m] < nums2[n]) {
                    num = nums1[m];
                    ++m;
                } else {
                    num = nums2[n];
                    ++n;
                }
            } else if (m == nums1.length) {
                num = nums2[n];
                ++n;
            } else if (n == nums2.length) {
                num = nums1[m];
                ++m;
            }

            ++total;

            if (remainder > 0) {
                //m,n总数为奇数 只需要找到(m+n)/2+1即可
                if (total == divisor + 1) {
                    return num;
                }
            } else {
                //m,n总数为偶数 需要找到 (m+n)/2 (m+n)/2 +1
                if (total == divisor) {
                    list.add(num);
                }
                if (total == divisor + 1) {
                    list.add(num);
                    return Double.valueOf(list.get(0) + list.get(1)) / 2;
                }
            }
        }
    }
}
